快速排序比冒泡排序要快的一种排序方法。其也是从冒泡排序演变而来的。之所以比冒泡排序快是因为使用了分治法。快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。
不同的是，冒泡排序在每一轮中只把 1 个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。 这种思路就叫作分治法。

假如给出一个 8 个元素的数列，一般情况下，使用冒泡排序需要比较 7 轮，每一轮把 1 个元素移动到数列的一端，时间复杂度是 O(n2)。在分治法的思想下，原数列在每一轮都被拆分成两部分，每一部分 在下一轮又分别被拆分成两部分，直到不可再分为止。每一轮的比较和交换，需要把数组全部元素都遍历一遍，时间复杂度是 O(n)。 这样的遍历一共需要多少轮呢?假如元素个数是 n，那么平均情况下需要 logn 轮，因 此快速排序算法总体的平均时间复杂度是 O(nlogn)。

```js
let arr = [2, 3, 4, 5, 6, 7, 8, 1];
let count = 0;
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let pivotIndex = Math.floor(arr.length / 2);
  let pivot = arr.splice(pivotIndex, 1)[0]; // 选取一个基准值
  let left = [],
    right = [];
  for (let i = 0; i < arr.length; i++) {
    count++;
    // 小于基准值放左边 否则放右边
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }
  // return quickSort(left).concat([pivot], quickSort(right));
  return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort(arr), `运行了${count}次`); // //[1,2,3,4,5,6,7,8] 运行了15次
```

### 基准元素的选择

最简单的方式是选择数列的第 1 个元素。

这种选择在绝大多数情况下是没有问题的。但是，假如有一个原本逆序的数
列，期望排序成顺序数列，那么会出现什么情况呢?

哎呀，整个数列并没有被分成两半，每一轮都只确定了基准元素的位置。
是呀，在这种情况下，数列的第 1 个元素要么是最小值，要么是最大值，根本无法发挥分治法的优势。

在这种极端情况下，快速排序需要进行 n 轮，时间复杂度退化成了 O(n2)。

那么，该怎么避免这种情况发生呢?
其实很简单，我们可以随机选择一个元素作为基准元素，并且让基准元素和数 列首元素交换位置

```js
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let pivotIndex = Math.floor(arr.length / 2);
  let pivot = arr.splice(pivotIndex, 1)[0];
  let left = [];
  let right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}
```
